package 链表;

import list.ListNode;

/**
 * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
 * 如果遇到需要删除头节点的题目，添加哨兵节点可以简化代码逻辑，请记住这个技巧.不能直接返回head节点
 * @author macy
 * @date 2025/11/4 16:01
 */
public class RemoveNthListNode {

    public static void main(String[] args) {

    }

    public ListNode removeNthFromEnd(ListNode head, int n) {

        if(head==null){
            return null;
        }
        ListNode dummy=new ListNode(-1,head);
        //快指针
        ListNode p1=dummy;
        //慢指针
        ListNode p2=dummy;
        int n1=n;
        while(n1>0){
          p1=p1.next;
          n1--;
        }

        while(p1.next !=null){
            p1=p1.next;
            p2=p2.next;
        }
        p2.next=p2.next.next;
        return dummy.next;
    }

    public ListNode removeNthFromEnd1(ListNode head, int n) {
        //
        ListNode dummy=new ListNode(-1,head);
        ListNode left=dummy;
        ListNode right=dummy;

        while(n>0){
            right=right.next;
            n--;
        }

        while(right.next!=null){
            right=right.next;
            left=left.next;
        }

        left.next=left.next.next;

        return dummy.next;
    }


}
